import java.util.Arrays;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:墨琦
 * Data:2023-04-21
 * Time:22:06
 */
public class TestHeap {
        public int[] elem;
        public int usedSize;

        public TestHeap() {
            this.elem = new int[10];
        }


        //创建一个大根堆  时间复杂度O(N)
        public void createHeap(int[] array) {
            for (int i = 0; i < array.length; i++) {
                elem[i] = array[i];
                usedSize++;
            }
            //把原始数据 给到了 elem数组
            for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
                shiftDown(parent,usedSize);
            }
        }

        /**
         *
         * @param parent 每棵子树的根节点
         * @param len 代表每棵子树的结束位置
         */
        private void shiftDown(int parent,int len) {
            int child = 2 * parent+1;
            //是不是一定有左孩子
            while (child < len) {
                //一定 不会越界 ！！！！
                if(child + 1 < len && elem[child] < elem[child+1]) {
                    child = child + 1;
                }
                if(elem[child] > elem[parent]) {
                    int tmp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = tmp;
                    parent = child;
                    child = 2 * parent+1;
                }
            }
        }


        public void push(int val) {
            //1. 检查满
            if(isFull()) {
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            //2、存数据
            elem[usedSize] = val;
            usedSize++;
            shiftUp(usedSize-1);
        }

        public boolean isFull() {
            return usedSize == elem.length;
        }

        public void shiftUp(int child) {
            int parent = (child-1)/2;
            while (child > 0) {
                if(elem[child] > elem[parent]) {
                    int tmp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = tmp;
                    child = parent;
                    parent = (child-1)/2;
                }else {
                    break;
                }
            }
        }

        public void poll() {
            if(empty()) {
                throw new HeapEmptyException("优先级队列是空的！");
            }
            int tmp = elem[0];
            elem[0] = elem[usedSize-1];
            elem[usedSize-1] = tmp;
            usedSize--;//9
            shiftDown(0,usedSize);
        }

        public boolean empty() {
            return usedSize == 0;
        }

        public int peek() {
            if(empty()) {
                throw new HeapEmptyException("优先级队列是空的！");
            }
            return elem[0];
        }

}
